package org.blogwu.learn.leetcode.链表;

public class _142_环形链表2 {
    public static void main(String[] args) {
        ListNode listNode10 = new ListNode(-5);
        ListNode listNode9 = new ListNode(-2, listNode10);
        ListNode listNode8 = new ListNode(-5, listNode9);
        ListNode listNode7 = new ListNode(-9, listNode8);
        ListNode listNode6 = new ListNode(6, listNode7);
        ListNode listNode5 = new ListNode(19, listNode6);
        ListNode listNode4 = new ListNode(-4, listNode5);
        ListNode listNode3 = new ListNode(7, listNode4);
        ListNode listNode2 = new ListNode(-7, listNode3);
        ListNode listNode1 = new ListNode(-1, listNode2);
        listNode10.next = listNode10;

        _142_环形链表2 hh = new _142_环形链表2();
        System.out.println(hh.detectCycle(listNode1).val);
    }


    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return null;
        ListNode first = head;
        // 1. 判断是否成环
        ListNode huan = this.hasCycle(head);
        if (huan == null) return null;
        // 2. 判断环有多长
        int count = this.cycleCount(huan);
        // 3. 计算入口
        ListNode snow = head;
        ListNode qq = head;
        //   qq先走count长度
        for (int i = 0; i < count; i++) {
            qq = qq.next;
        }

        while ((snow.val != qq.val) || (snow.next != qq.next)) {
            snow = snow.next;
            qq = qq.next;
        }
        return snow;
    }

    /**
     * 计算环长度
     *
     * @param head 相遇节点
     * @return
     */
    public int cycleCount(ListNode head) {
        ListNode temp = head;
        int i = 1;
        while (true) {
            temp = temp.next;
            if ((temp.val == head.val) && (temp.next == head.next)) {
                return i;
            }
            i++;
        }

    }


    /**
     * 快指针走两步，慢指针走一步
     *
     * @param head
     * @return
     */
    public ListNode hasCycle(ListNode head) {
        ListNode snow = head;
        int i = 0;
        while (true) {
            head = head.next;
            if (head == null) {
                return null;
            }
            if (i > 2) {
                snow = snow.next;
                if ((head.val == snow.val) && (head.next == snow.next)) {
                    return snow;
                }
                i = 0;
            } else {
                i++;
            }
        }
    }
}
